// Copyright (C) 2012 Yury Bychenkov (http://bychenkov.com).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//  - Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//  - Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//  - Neither the name of Yury Bychenkov nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

template <typename ElementTraits>
DictionaryBuilder<ElementTraits>::DictionaryBuilder(uint8* memory, size_t memorySize, uint8* externalMemory_, size_t externalMemoryCapacity_):
	dataStart(memory),
	dataEnd(memory + (((memorySize * 87) / 100) & ~7)),
	bufferEnd(memory + memorySize),

	externalMemory(externalMemory_),
	externalMemoryCapacity(externalMemoryCapacity_),
	externalMemoryPos(0),

	chunks(0),
	chunkCapacity(1024),
	externalChunkCount(0),
	lastChunkIndex(0)
{
	chunks = new Chunk[chunkCapacity];

	Chunk& chunk = chunks[0];
	chunk.first = dataStart;
	chunk.last = 0;
	chunk.end = dataStart;
	chunk.count = 0;
}

template <typename ElementTraits>
DictionaryBuilder<ElementTraits>::~DictionaryBuilder() {
	if (chunks != 0) {
		delete [] chunks;
	}
}

template <typename ElementTraits>
void DictionaryBuilder<ElementTraits>::copyMemory(uint8* dst, const uint8* src, const uint size) {
	if (size > 0) ::memmove(dst, src, size);
/*	for(uint i = 0; i < size; i++) {
		dst[i] = src[i];
	}*/
}

template <typename ElementTraits>
bool DictionaryBuilder<ElementTraits>::build(uint8* buffer, uint64 capacity, uint64& size, uint& count) {
	if (lastChunkIndex == 0 && chunks[0].count == 0) {
		count = 0;
		size = 0;
		return true;
	}

	size = flush(buffer, capacity, false);
	if (size == 0) {
		return false;
	}

	Chunk& chunk = chunks[0];

	count = chunk.count;

	chunk.first = dataStart;
	chunk.last = 0;
	chunk.end = dataStart;
	chunk.count = 0;

	externalMemoryPos = 0;
	lastChunkIndex = 0;

	return count;
}


template <typename ElementTraits>
bool DictionaryBuilder<ElementTraits>::add(const uint8* element) {
	const uint elementSize = ElementTraits::sizeOf(element);

	while (chunks[lastChunkIndex].end + elementSize > dataEnd || lastChunkIndex - externalChunkCount >= MAX_INNER_CHUNKS) {
		if (lastChunkIndex > 0) {
			if (merge()) {
				continue;
			}
		}
		if (chunks[lastChunkIndex].count > 0) {
			uint64 size = flush(externalMemory + externalMemoryPos, externalMemoryCapacity - externalMemoryPos, true);
			if (size == 0) {
				return false;
			}
			externalMemoryPos += size;
			continue;
		}
		return false;
	}

	Chunk& lastChunk = chunks[lastChunkIndex];

	int cmp = chunks[lastChunkIndex].count == 0? 1: ElementTraits::compare(element, chunks[lastChunkIndex].last);

	if (cmp == 0) {
		return true;
	} else if (cmp > 0) {
		copyMemory(lastChunk.end, element, elementSize);
		lastChunk.last = lastChunk.end;
		lastChunk.end += elementSize;
		lastChunk.count++;
	} else if (lastChunk.count == 1) {
		Chunk& lastChunk = chunks[lastChunkIndex];
		copyMemory(lastChunk.first + elementSize, lastChunk.first, lastChunk.end - lastChunk.first);
		copyMemory(lastChunk.first, element, elementSize);
		lastChunk.last = lastChunk.first + elementSize;
		lastChunk.end += elementSize;
		lastChunk.count++;
	} else {
		if (lastChunkIndex == chunkCapacity - 1) {
			uint newChunkCapacity = chunkCapacity + 1024;
			Chunk* newChunks = new Chunk[newChunkCapacity];
			copyMemory((uint8*) newChunks, (uint8*) chunks, chunkCapacity * sizeof(Chunk));
			delete [] chunks;
			chunks = newChunks;
			chunkCapacity = newChunkCapacity;
		}

		Chunk& newChunk = chunks[++lastChunkIndex];

		newChunk.first = chunks[lastChunkIndex - 1].end;
		newChunk.last = newChunk.first;
		newChunk.end = newChunk.last + elementSize;
		newChunk.count = 1;
		
		copyMemory(newChunk.first, element, elementSize);

		return true;
	}

	while (lastChunkIndex > externalChunkCount && chunks[lastChunkIndex].count >= chunks[lastChunkIndex - 1].count) {
		if (!merge()) {
			break;
		}
	}

	return true;
}


template <typename ElementTraits>
bool DictionaryBuilder<ElementTraits>::merge() {

	Chunk& chunk1 = chunks[lastChunkIndex - 1];
	Chunk& chunk2 = chunks[lastChunkIndex];

	if (chunk1.end != chunk2.first) {
		return false;
	}

	lastChunkIndex--;

	int cmp = ElementTraits::compare(chunk1.last, chunk2.first);
	if (cmp < 0) {
		chunk1.last = chunk2.last;
		chunk1.end = chunk2.end;
		chunk1.count += chunk2.count;
		return true;
	}

	if (cmp == 0) {
		if (chunk2.count > 1) {
			uint firstElementSize = ElementTraits::sizeOf(chunk2.first);
			copyMemory(chunk2.first, chunk2.first + firstElementSize, chunk2.end - chunk2.first - firstElementSize);
			chunk1.last = chunk2.last - firstElementSize;
			chunk1.end = chunk2.end - firstElementSize;
			chunk1.count += chunk2.count - 1;
		}
		return true;
	}

	uint8* first1 = chunk1.first;
	uint8* const last1 = chunk1.last;

	uint8* first2 = chunk2.first;
	uint8* const last2 = chunk2.last;

	uint equalCount = 0;

	// Skip common prefix
	while ((cmp = ElementTraits::compare(first1, first2)) < 0) {
		first1 += ElementTraits::sizeOf(first1);
   	}

   	while (cmp == 0) {
   	    equalCount++;

		const uint elementSize = ElementTraits::sizeOf(first1);

		first2 += elementSize;
		if (first2 > last2) return true;

		first1 += elementSize;
		if (first1 > last1) {
			copyMemory(chunk1.end, first2, chunk2.end - first2);
			chunk1.end += chunk2.end - first2;
			chunk1.last = chunk1.end - (chunk2.end - chunk2.last);
			chunk1.count += chunk2.count - equalCount;
			return true;
		}

		cmp = ElementTraits::compare(first1, first2);
   	}


	assert(first1 <= last1 && first2 <= last2 && cmp > 0);

	uint8* o = first1;
	uint8* buffer = chunk2.end;
	
	if (bufferEnd - buffer < chunk2.end - first1) {
		lastChunkIndex++;
		return false;
	}

	while (true) {
		if (cmp > 0) {
			const uint elementSize = ElementTraits::sizeOf(first2);
			copyMemory(buffer, first2, elementSize);
			first2 += elementSize;
			buffer += elementSize;
			if (first2 > last2) break;
		} else {
			const uint elementSize = ElementTraits::sizeOf(first1);
			copyMemory(buffer, first1, elementSize);
			first1 += elementSize;
			buffer += elementSize;
			if (cmp == 0) {
				equalCount++;
				first2 += elementSize;
				if (first2 > last2) break;
			}
			if (first1 > last1) break;
		}

		cmp = ElementTraits::compare(first1, first2);
	}

	if (first1 <= last1) {
		copyMemory(buffer, first1, chunk1.end - first1);
		buffer += chunk1.end - first1;
		first1 = chunk1.end;

		copyMemory(o, chunk2.end, buffer - chunk2.end);
		chunk1.end = o + (buffer - chunk2.end);
		chunk1.last = chunk1.end - (first1 - last1);
	} else {
		copyMemory(o, chunk2.end, buffer - chunk2.end);
		o += buffer - chunk2.end;
		if (first2 > o && first2 <= last2) {
			copyMemory(o, first2, chunk2.end - first2);
		}
		chunk1.end = o + (chunk2.end - first2);
		chunk1.last = chunk1.end - (chunk2.end - chunk2.last);
	}

	chunk1.count += chunk2.count - equalCount;

	return true;
}

template <typename ElementTraits>
uint64 DictionaryBuilder<ElementTraits>::flush(uint8* buffer, uint64 capacity, bool mainOnly) {
	assert (chunks[lastChunkIndex].count > 0);

	const uint chunkIndex1 = mainOnly? externalChunkCount: 0;
	const uint chunkIndex2 = chunks[lastChunkIndex].count > 0? lastChunkIndex: lastChunkIndex - 1;

	if (chunkIndex1 == chunkIndex2) {
		Chunk& chunk = chunks[chunkIndex1];
		if (chunk.end - chunk.first > (ptrdiff_t) capacity) {
			return 0;
		}
		copyMemory(buffer, chunk.first, chunk.end - chunk.first);

		ptrdiff_t shift = buffer - chunk.first;

		chunk.first = buffer;
		chunk.last += shift;
		chunk.end += shift;
	} else {
    
		int heapSize = chunkIndex2 + 1 - chunkIndex1;

		Chunk** heap = new Chunk*[heapSize];
		for (int i = heapSize - 1; i >= 0; i--) {
			heap[i] = &chunks[i + chunkIndex1];
			heap[i]->current = heap[i]->first;
			fixHeap(heap, heapSize, i);
		}

		uint count = 0;        
        uint8* dest = buffer;
		while (true) {
			const uint8* element = heap[0]->current;
			const uint elementSize = ElementTraits::sizeOf(element);
        
			for (bool duplicate = true; duplicate; duplicate = (0 == ElementTraits::compare(heap[0]->current, element))) {
				if (heap[0]->current == heap[0]->last) {
					if (--heapSize == 0) break;
					heap[0] = heap[heapSize];
				} else {
					heap[0]->current += elementSize;
				}
				fixHeap(heap, heapSize, 0);
			}
        
            if (elementSize > capacity) {
            	delete [] heap;
            	return 0;
            }

            copyMemory(dest, element, elementSize);
            dest += elementSize;
            capacity -= elementSize;
			count++;
    
			if (heapSize == 0) {
				Chunk& chunk = chunks[chunkIndex1];
				chunk.first = buffer;
				chunk.end = dest;
				chunk.last = dest - elementSize;
				chunk.count = count;
        		delete [] heap;
				break;
			}
		}
	}

	lastChunkIndex = externalChunkCount = chunkIndex1 + 1;

	Chunk& chunk = chunks[lastChunkIndex];
	chunk.first = dataStart;
	chunk.last = 0;
	chunk.end = dataStart;
	chunk.count = 0;
	
	return chunks[chunkIndex1].end - chunks[chunkIndex1].first;
}

    
template <typename ElementTraits>
void DictionaryBuilder<ElementTraits>::fixHeap(Chunk** heap, int heapSize, int nodeIndex) {
	while (nodeIndex < heapSize) {
		int leftChildIndex = nodeIndex * 2 + 1;
		if (leftChildIndex >= heapSize) {
			return;
		}
		int rightChildIndex = leftChildIndex + 1;
	
		if (ElementTraits::compare(heap[nodeIndex]->current, heap[leftChildIndex]->current) <= 0) {
			if (rightChildIndex < heapSize && ElementTraits::compare(heap[nodeIndex]->current, heap[rightChildIndex]->current) > 0) {
				swap(heap[nodeIndex], heap[rightChildIndex]);
				nodeIndex = rightChildIndex;
			} else {
				return;
			}
		} else {
			if (rightChildIndex < heapSize && ElementTraits::compare(heap[leftChildIndex]->current, heap[rightChildIndex]->current) > 0) {
				swap(heap[nodeIndex], heap[rightChildIndex]);
				nodeIndex = rightChildIndex;
			} else {
				swap(heap[nodeIndex], heap[leftChildIndex]);
				nodeIndex = leftChildIndex;
			}
		}
	}
}

inline Dictionary::Dictionary(const uint8* data_, uint dataSize_, uint dataCount_, const uint32* skipTable_, uint skipStep_):
	data(data_),
	dataSize(dataSize_),
	dataCount(dataCount_),
	skipTable(skipTable_),
	skipStep(skipStep_),
	skipCount((dataCount - 1) / skipStep + 1)
{
	
}

inline uint Dictionary::getCount() const {
	return dataCount;
}

template <typename ElementTraits>
int Dictionary::find(const void* element) const {
	uint i1 = 0;
	uint i2 = skipCount;

	while (i1 + 1 < i2) {
		int i = (i1 + i2) / 2;
		int cmp = ElementTraits::compare((const uint8*) element, data + skipTable[i]);
		if (cmp < 0) {
			i2 = i;
		} else if (cmp > 0) {
			i1 = i;
		} else {
			return i * skipStep;
		}
	}

	const uint8* p = data + skipTable[i1];
	uint i = 0;
	uint n = (i1 + 1 < skipCount)? skipStep: (dataCount - i1 * skipStep);
	for (; i < n; i++) {
		int cmp = ElementTraits::compare((const uint8*) element, p);
		if (cmp > 0) {
			p += ElementTraits::sizeOf(p);
	    } else if (cmp == 0) {
	    	return i1 * skipStep + i;
	    } else {
		    break;
	    }
	}
	return -(i1 * skipStep + i + 1);
}

template <typename ElementTraits>
const uint8* Dictionary::get(uint elementIndex) const {
	if (elementIndex >= dataCount) {
		return 0;
	}
	
	const uint8* element = data + skipTable[elementIndex / skipStep];
	for (uint i = elementIndex % skipStep; i > 0; i--) {
		element += ElementTraits::sizeOf(element);
	}

	return element;
}
